class Solution(object):
    def findDerangement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 0
        if n == 2:
            return 1
        DP = [0, 1, 0]
        for i in range(2, n):
            DP[i % 3] = (DP[(i - 2) % 3] * i % (10**9 + 7) + DP[(i - 1) % 3] * i % (10**9 + 7)) % (10**9 + 7)
        return DP[(n - 1) % 3]

data = Solution()
n = 4
print(data.findDerangement(n))
